\documentclass[a4paper,10pt]{report}
\usepackage[utf8]{inputenc}
\setlength{\parindent}{0mm} 
\usepackage{amsmath}
\usepackage{graphicx}
\title{Assignment 4 Solution}
\author{}

\begin{document}
\maketitle
\section*{Task 1}
The code balance of a loop is defined as $$B_c = \frac{\text{data traffic}}{\text{floating point operations}} \left[ \frac{\text{Words}}{\text{Flops}} \right].$$
\subsection*{a) STREAM add}
The add kernel has 3 + 1 words and one flop (including write allocate), thus the code balance is 4.0 W/F.
\subsection*{b) Matrix-vector multiply}
Here, $y(j)$ can be kept in a register so that write allocate can be excluded.
$$B_c = \frac{2}{2} = 1~W/F$$
\subsection*{c) Scalar ratio}
Assuming division has 4 flops, write allocate can be again excluded since $s$ can be stored in the register.
$$B_c = \frac{2}{5} = 0.4~ W/F$$
\subsection*{d) JDS sparse matrix-vector product}
Only counting the explicit load operations, the code balance is 
$$B_c = \frac{3}{2} = 1.5~ W/F.$$

\section*{Task 2}
\begin{figure}[h]
   \centering
   \includegraphics[width=\textwidth]{./GScode.png}
   \caption{Gauss-Seidel code}
\end{figure}

One of the first steps proposed to improve the performance of the Gauss-Seidel smoother is to introduce a red-black ordering of the points. 
This is done with the aim of eliminating the dependencies in the computation of new elements in the array. 
Since the computation of each red point will depend only on black points and vice versa. The following is the proposed implementation.

\begin{figure}[h]
   \centering
   \includegraphics[width=\textwidth]{./GSRBcode.png}
   \caption{Red-black Gauss-Seidel code}
\end{figure}

It can be observed that with the red-black ordering scheme the carried-loop dependencies are avoided but further improvements can be done. 
If both, red and black points, are stored in a single array the cache lines will contain again both read and black points, 
and since the computation of one point only requires points of the same color, the cache line will not be use efficiently because half 
of it will not be used. For this reason the second step to improve the code would be use two arrays, one for each color.

\end{document}          
